package org.nowcoder.leetcode.BTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * Title  : 113. Path Sum II
 * Source : https://leetcode.cn/problems/path-sum-ii/description/
 * Author : XrazYang
 * Date   : 2023-09-09
 */

public class LeetCode_113 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private Deque<Integer> deque = new ArrayDeque<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        // 非递归实现
        // List<List<Integer>> results = new ArrayList<>();
        // if (root == null) {
        //     return results;
        // }

        // ArrayDeque<TreeNode> sta = new ArrayDeque<>();
        // ArrayDeque<List<Integer>> sumSta = new ArrayDeque<>();
        // sta.push(root);
        // sumSta.push(new ArrayList<>() {{
        //     add(root.val);
        // }});
        // while (!sta.isEmpty()) {
        //     TreeNode node = sta.pop();
        //     List<Integer> sum = sumSta.pop();

        //     if (node.left == null && node.right == null) {
        //         if (sum.stream().mapToInt(Integer::intValue).sum() == targetSum) {
        //             results.add(sum);
        //         }
        //     }

        //     if (node.right != null) {
        //         sta.push(node.right);
        //         ArrayList<Integer> temp = new ArrayList<>(sum);
        //         temp.add(node.right.val);
        //         sumSta.push(temp);
        //     }

        //     if (node.left != null) {
        //         sta.push(node.left);
        //         ArrayList<Integer> temp = new ArrayList<>(sum);
        //         temp.add(node.left.val);
        //         sumSta.push(temp);
        //     }
        // }
        // return results;

        //递归实现
        List<List<Integer>> results = new ArrayList<>(); //保存结果
        ldfs(root, targetSum, results);
        return results;
    }

    public void ldfs(TreeNode root, int targetSum, List<List<Integer>> results) {
        if (root != null) {
            deque.offerLast(root.val);
            if (root.left == null && root.right == null && root.val == targetSum) {
                results.add(new ArrayList<>(deque));
            }
            targetSum -= root.val;
            ldfs(root.left, targetSum, results);
            ldfs(root.right, targetSum, results);
            deque.pollLast(); // 叶子结点不等，弹出
        }
    }
}
